package 极客算法训练营.chapter10;

import java.util.Deque;
import java.util.LinkedList;

public class 柠檬水找零 {
    class Solution {
        public boolean lemonadeChange(int[] bills) {
            if (bills == null || bills.length <= 1) {
                return true;
            }
            Deque<Integer> deque = new LinkedList<>();
            for (int i = 0; i < bills.length; i++) {
                if (bills[i] == 5) {
                    //如果是5就加到队列首部
                    deque.addFirst(bills[i]);
                } else if (bills[i] == 10) {
                    if (deque.size() < 1) return false;
                    //先找钱
                    Integer poll = deque.pollFirst();
                    if (poll != 5) return false;
                    //如果是10就加到队列尾部
                    deque.addLast(bills[i]);
                } else {
                    if (deque.size() < 2) return false;
                    //抽一张最小的，抽一张最大的
                    Integer first = deque.pollFirst();
                    Integer last = deque.pollLast();
                    //分三种情况：5-5  5-10  10-10
                    if (first == 5 && last == 10) continue;
                    if (first == 10 && last == 10) return false;
                    if (deque.size() == 0) return false;
                    else deque.pollFirst();//首尾都是5，剩下的都是5
                }
            }
            return true;
        }
    }
}
